Conventional adder/subtractor circuits are used in configurable logic devices to perform the most common arithmetic operations. FIG. 1 is a schematic diagram of a conventional carry chain circuit, which receives three input signals A, B, and Cin, where Cin is a carry input signal received from another carry chain multiplexer circuit. Input signals A and B are applied to input terminals of XOR gate 101A. In response, XOR gate 101A provides a carry propagate signal, P.
Carry propagate signal P is applied to an input terminal of XOR gate 102. Carry input signal Cin is applied to the other input terminal of XOR gate 102. In response, XOR gate 102 provides a sum signal S. Table 1 depicts the truth table for the carry chain circuit shown in FIG. 1.
TABLE 1ABCinPSumCout000000100110010110110001001010101101011101111011
FIG. 2 depicts the subtraction operation A-B by using a conventional logic device. The carry propagate signal P is also applied to a control input terminal of multiplexer 103. Input signal A is applied to the “0” input terminal of multiplexer 103 and the carry input signal Cin is provided to the “1” input terminal of multiplexer 103. Depending upon the value of carry propagate signal P, either input signal A or carry input signal Cin is transmitted through multiplexer 103 as carry output signal Cout. The XNOR gate 101B is used here instead of the XOR gate 101A. This is equivalent to inverting input B and using XOR gate 101A instead.
Implementation of subtraction operation by using two's complement operation is shown in Table 2
TABLE 2ABBinPDiff(P xor Bin)Bout000110100001010000110110001101101011011010111101Carry/Borrow chain circuits shown in FIG. 1 and FIG. 2 have been implemented in a number of different ways in programmable logic devices (PLDs) such as field programmable-gate-arrays-(FPGAs).
A conventional circuit for using a function generator of a programmable logic device to implement carry logic functions is described by the U.S. Pat. No. 5,818,255 that shows one of the methods of implementing the aforementioned truth tables in PLDs. The circuit is further illustrated diagrammatically in FIG. 3. The configurable bits 320 and 401-416 are programmed with appropriate values to implement the truth tables shown in Table 1 and Table 2. Signal G is connected to “A” or “B”. It can be easily observed from the aforementioned U.S. Patent that it does not have a dedicated provision to cascade the output S of the 4-input LUT for implementing wide input cascade functions.
Another conventional circuit for implementing dynamic addition subtraction operation is shown in FIG. 4 that perform dynamic addition subtraction in 2's complement form by configuring input G3 or input G4 of the LUT as the add-sub signal and then using some additional logic so that the “cin” may become either “0” for addition or “1” for subtraction, since the operation is 2's complement. It is noteworthy that the add-sub signal needs to be connected at two places that is one at the LUT inputs (G3 or G4) and the other at the logic required for initializing the chain to logic 0 or logic 1. MUXCY is used for implementing carry logic as well as for implementing wide input functions by cascading the outputs of the 4-input LUTs. However the cascade element (MUXCY) does not have any provision of implementing XOR gates. Furthermore, additional connectivity in the logic circuit requires an increase in the resources.
An existing Altera device shown in FIG. 5A provides an XOR gate (501) at the input “data1” of the LUT. This XOR gate is specifically given for performing dynamic addition/subtraction using 2's complement logic. However providing an XOR gate at only one input of the LUT causes the logical equivalence of the two arithmetic inputs “data1” and “data2” to be lost when performing dynamic addition subtraction operation since only “data2±data1” operation can be performed and not “data1±data2” operation. If this equivalence is required then additionally connectivity has to be provided at the input terminals for “data1” and “data2” so that any signal that reaches “data1” can also reach “data2” and vice-versa any signal that reaches “data2” can also reach “data1”. This causes an additional increase in hardware resources due to more connectivity and therefore requires more configuration bits.
Table 3 shows the truth table for the subtraction operation for performing A-B in 2's complement form.
TABLE 3ABBin(2scomp)DBout(2scomp)0001010001010001101000101101110111011101The Bin(2scomp) represents the Bout(2scomp) of the previous subtraction operation. At the start of the subtraction operation Bin(2scomp) is given a fixed value of logic 1 at-the-LSB.
Equation for a 2s complement subtraction(A-B) operation can be written as:Diff=˜B^A^Bin(2scomp)  (1)Bout(2scomp)=(˜B&&A)∥(˜B&&Bin(2scomp))∥(Bin(2scomp)&&A)  (2).
Here, it is assumed that the operation (101011-110100) that is equivalent to −21-(−12) has to be performed using 2's complement operation, which is illustrated in detail by FIG. 5B. Also shown are the borrow outs of each stage. The result is 110111, which is the binary representation of −9 in 2's complement form. As can be seen from this example that at the LSB “Bin (2scomp)” requires a value of logic 1. This is shown as “init” in FIG. 5B.
All of the above prior art approaches implement subtraction using the two's complement arithmetic. The subtraction is performed by simply inverting one of the operands and making “Cin” as logic 1 for the LSB subtraction. Using two's complement arithmetic it suffices to provide just an adder circuit and generates the requirement of more hardware resources.
Thus, there is a need for an improved logic device that provides a scalable approach for achieving a minimum hardware implementation of arithmetic operations on n-bit variables.